#include <iostream>
#include <vector>
using namespace std;

void shellSort(vector<int>& res){
	int i,j,gap;
	int len = res.size();
	for(gap = len / 2 ; gap > 0 ; gap /= 2){
		for(i = 0 ; i < gap ; i++){
			for(j = i + gap ; j < len ; j += gap ){
				if(res[j] < res[j - gap]){
					int tmp = res[j];
					int k = j - gap;
					while(k >= 0 && res[k] > tmp){
						res[k + gap] = res[k];
						k -= gap;
					}
					res[k + gap] = tmp;
//					int k = j;
//					while(k > 0 && res[k] < res[k - gap]){
//						swap(res[k] , res[k - gap]);
//						k -= gap;
//					}
				}
			}
		}
	}
	
} 

int main(){
	int arr[] = {12,45,1,34,87,-3,822,23,32};
	vector<int> res(arr,arr+9);
	shellSort(res);
	vector<int>::iterator ite = res.begin();
	for(;ite != res.end();ite++){
		cout<< *ite <<" ";
	}
	system("pause");
	return 0;
}
